package com.example.demo.search;

/**
 * 二分查找:
 * <p>
 * 时间复杂度：O(logn)
 * 空间复杂度：O()
 *
 * @author WangYX
 * @version 1.0.0
 * @date 2024/01/26 13:55
 */
public class BinarySearch {

    /**
     * 循环实现二分查找
     *
     * @author WangYX
     * @date 2024/01/26 14:31
     */
    public static int binarySearch(int[] arr, int key) {
        //第一个下标
        int low = 0;
        //最后一个下标
        int high = arr.length - 1;
        int mid = 0;
        //防越界
        if (key < arr[low] || key > arr[high] || low > high) {
            return -1;
        }
        while (low <= high) {
            mid = ((high - low) >>> 1) + low;
            if (key < arr[mid]) {
                high = mid - 1;
            } else if (key > arr[mid]) {
                low = mid + 1;
            } else {
                return mid;
            }
        }
        return -1;
    }

    /**
     * 递归实现二分查找
     *
     * @author WangYX
     * @date 2024/01/26 14:38
     */
    private static int binarySearch(int[] nums, int target, int left, int right) {
        if (left <= right) {
            int mid = ((right - left) >>> 2) + left;
            if (nums[mid] > target) {
                return binarySearch(nums, target, left, mid - 1);
            } else if (nums[mid] < target) {
                return binarySearch(nums, target, mid + 1, right);
            } else if (nums[mid] == target) {
                return mid;
            }
        }
        return -1;
    }


}
